CF398B Painting The Wall

先考虑所有格子均未涂色的情况。

因为格子的涂色只会影响一行一列，所以可以设 $dp(i,j)$ 表示还需要涂 $i$ 行 ， $j$ 列的期望步数。

1.涂色格所在行列均未染色，由 $dp(i-1,j-1)$ 转移，概率为 $\frac{i}{n} \times \frac{j}{n}$

2.涂色格所在行未染色，列已染色，由 $dp(i-1,j) $ 转移，概率为 $\frac{i}{n} \times \frac{n-j}{n}$

3.涂色格所在列未染色，行已染色，由 $dp(i,j-1) $ 转移，概率为 $\frac{n-i}{n} \times \frac{j}{n}$

4.涂色格所在行列均已染色，由 $dp(i,j)$ 转移，概率为 $\frac{n-i}{n} \times \frac{n-j}{n}$

综上得：

$dp(i,j) = 1 + dp( i - 1 , j ) * \frac{i * ( n - j )}{n^2} + dp( i , j - 1 ) * \frac{( n - i ) * j}{n^2} + dp( i - 1 , j - 1 ) * \frac{i * j}{n^2} + dp(i,j) * \frac{(n-i)*(n-j)}{n^2}$

移项得：

$dp(i,j) = \frac{ 1 + dp( i - 1 , j ) * \frac{i * ( n - j )}{n^2} + dp( i , j - 1 ) * \frac{( n - i ) * j}{n^2} + dp( i - 1 , j - 1 ) * \frac{i * j}{n^2} }{1-\frac{(n-i)(n-j)}{n^2}}$

上下同时乘 $n^2$ 得到：

$dp(i,j) = \frac{ n^2 + dp( i - 1 , j ) * i * ( n - j ) + dp( i , j - 1 ) * ( n - i ) * j + dp( i - 1 , j - 1 ) * i * j }{n^2-(n-i)(n-j)}$

边界条件：

1.$dp[0][0]=0$

2.$dp[0][i]/dp[i][0]=\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor$ 经典的邮票收集问题。

现在再考虑一开始有涂色的格子，其实只是让其中一些行列提前满足要求，即答案并不是 $dp(n,n)$ ，而是减去已满足数量的结果自己意会一下。

#include <cstdio>

const int MAXN = 2e3;
int n , m , x , y;
bool vis[ 2 ][ MAXN + 5 ];
double dp[ MAXN + 5 ][ MAXN + 5 ];

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 , u , v ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v);
		if( !vis[ 0 ][ u ] ) x -= ( vis[ 0 ][ u ] = 1 );
		if( !vis[ 1 ][ v ] ) y -= ( vis[ 1 ][ v ] = 1 );
	}
	x += n , y += n;

	dp[ 0 ][ 0 ] = 0;
	for( int i = 1 ; i <= n ; i ++ ) {
		dp[ i ][ 0 ] = dp[ i - 1 ][ 0 ] + n * 1.0 / i;
		dp[ 0 ][ i ] = dp[ 0 ][ i - 1 ] + n * 1.0 / i;
	}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ )
			dp[ i ][ j ] = ( n * n + dp[ i - 1 ][ j ] * i * ( n - j ) + dp[ i ][ j - 1 ] * ( n - i ) * j + dp[ i - 1 ][ j - 1 ] * i * j ) / ( n * n - ( n - i ) * ( n - j ) );

	printf("%.10f", dp[ x ][ y ] );
	return 0;
}